package com.xiayuanxing.arithmetic.DataStructures.Tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @program: arithmetic
 * @description: 赫夫曼树
 * @author: xia yuan xing
 * @create: 2021-10-09 11:48
 */
public class HuffmanTree {



    public static void main(String[] args) {

        int arrp[] = {13,7,8,3,29,6,1};

        Node root = createHuffmanTree(arrp);
        System.out.println(root);

        preOrder(root);
    }


    /**
     * 赫夫曼树前序遍历
     * @param root
     */
    public static void preOrder(Node root){
        if (root != null){
            root.preOrder();
        }else {
            System.out.println("这课二叉树是空树");
        }
    }


    /**
     * 创建赫夫曼树的方法
     * @param arr
     * @return 赫夫曼书顶级节点
     */
    public static Node createHuffmanTree(int[] arr){
        //1.将Node放进list中
        List<Node> nodes = new ArrayList<Node>();
        for (int value: arr) {
            nodes.add(new Node(value));
        }
        while (nodes.size() > 1){
            //2.排序
            Collections.sort(nodes);
            //3.取出根节点权值最小的两颗二叉树
            Node left = nodes.get(0);
            Node right = nodes.get(1);
            //4.构建一颗新的二叉树
            Node parent = new Node(left.value + right.value);
            parent.left = left;
            parent.right = right;
            //5.从list中删除处理过的二叉树
            nodes.remove(left);
            nodes.remove(right);
            //6.将parent加入nodes
            nodes.add(parent);
        }
        return nodes.get(0);
    }

}




class Node implements Comparable<Node>{
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }


    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }

    @Override
    public int compareTo(Node o) {

        //从小到大排序
        return this.value - o.value;

        //从大到小排序
//        return -(this.value - o.value);
    }


    /**
     * 前序遍历
     */
    public void preOrder(){
        System.out.println(this);

        if (this.left != null){
            this.left.preOrder();
        }
        if (this.right != null){
            this.right.preOrder();
        }
    }
}